package argo.hot100.linklist;


import java.util.HashSet;
import java.util.Set;



public class GetIntersectionNode {

    public ListNode getIntersectionNodeHash(ListNode headA, ListNode headB) {
        ListNode res = null;
        Set<ListNode> hash = new HashSet<>();
        while (headA != null) {
            hash.add(headA);
            headA = headA.next;
        }

        while (headB != null) {
            if (hash.contains(headB)) {
                res = headB;
                break;
            }
            headB = headB.next;
        }

        return res;
    }


    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode res = null;
        ListNode pa = headA, pb = headB;
        while (pa.next != null && pb.next != null) {
            pa = pa.next;
            pb = pb.next;
        }
        while (pa.next != null ) {
            pa=pa.next;
            headA = headA.next;
        }
        while (pb.next != null ) {
            pb=pb.next;
            headB = headB.next;
        }
        //process last node
        if (pa!=pb) {
            return null;
        }
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }


        return headA;
    }
}
